// utility, collection, etc
define(
  ["require"],
  function(require) {

    //  a double linked list, list node is
    // { _h: <list internal head node>, p: <prev node>, n: <next node>, v: <node value> }

    function LinkedList() {
       this._len = 0;
       this._head = {};  // internal node act as head/tail, turn list into a cycle.
       this._head.n = this._head;
       this._head.p = this._head;
    }

    // no method return node value, all return node, caller use node.v to get value.

    LinkedList.prototype.size = function() {
       return this._len;
    }

    LinkedList.prototype.first = function() {
       return (this._head.n == this._head ? null : this._head.n);
    }

    LinkedList.prototype.last = function() {
       return (this._head.p == this._head ? null : this._head.p);
    }

    LinkedList.prototype.addFirst = function(nodeVal) {
       var node = { v : nodeVal };
       node._h = this._head;
       node.p = this._head;
       node.n = this._head.n;
       node.n.p = node;
       node.p.n = node;
       this._len += 1;
       return node;
    }

    LinkedList.prototype.remove = function(node) {
       if (!node || node._h != this._head || node == this._head)
          return;

       node.p.n = node.n;
       node.n.p = node.p;
       delete node.p;
       delete node.n;
       delete node.h;
       this._len -= 1;
    }

    LinkedList.prototype.removeLast = function() {
       var node = this.last();
       this.remove(node);
       return node;
    }

    LinkedList.prototype.moveToFirst = function(node) {
        if (!node || node._h != this._head || node == this._head)
            return;
        node.p.n = node.n;
        node.n.p = node.p;
        node._h = this._head;
        node.p = this._head;
        node.n = this._head.n;
        node.n.p = node;
        node.p.n = node;
     }
    
    LinkedList.prototype.clear = function() {
       this._head.n = this._head;
       this._head.p = this._head;
       this._len = 0;
    }

    return {
      LinkedList : LinkedList,
    }
  }
);

